#import math

"""
    Generates prime numbers, in sequence, based on 
    the Sieve of Eratosthenes.
"""
def primes():
    yield 2

    n = 3
    primes = {}
    primes[n] = n**2

    while True:
        yield n
        n += 2
        while n in primes.values():
            for k,v in primes.iteritems():
                if v == n:
                    primes[k] += k*2
            n += 2
        primes[n] = n**2


"""
    Generates triangle numbers, in sequence, starting from 1.
"""
def triangles():
    n = 1
    while True:
        yield sum(xrange(1, n+1))
        n += 1


"""
    Returns a list of pairs of factors for the given integer.
"""
from math import ceil, sqrt
from itertools import chain
def factors(num):
     c = chain.from_iterable([(n,num/n) for n in range(1,int(ceil(sqrt(num)))+1) if num%n==0])
     s = set(list(c))
     l = list(s)
     l.sort()
     return l
#def factors(num):
#    return [(n,num/n) for n in range(2,int(math.ceil(math.sqrt(num)))) if num%n==0]


"""
    Returns the greatest common denominator for the given
    integers. If the return value is 1, that means that 
    a and b are coprime.
"""
def gcd(a, b):
    if a>b:
        return gcd(b, a)
    elif b%a==0:
        return a
    else:
        return gcd(b%a, a)
